package com.lry.triTree;

import com.lry.easyExcel.utils.StringUtils;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author JiangJie
 * @create 2020-12-09 11:27
 */
public class TriTree {

    private Node root;

    /**
     * 插入一个新节点，计算插入后的路径，更新节点所有上级的角色
     * @param bathPath 基础路径
     * @param userNode
     * @return 插入之后的路径
     */
    public void insert(String bathPath,UserNode userNode){
        StringBuilder sb = new StringBuilder();
        sb.append(StringUtils.isEmpty(bathPath)?"":bathPath+",");

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            Node cur = queue.poll();

            if(null!=cur.line1){
                queue.offer(cur.line1);
            }else{
                if(canAdd(userNode.parentId,cur)){
                    cur.line1 = new Node(userNode.id,parent(cur,userNode.parentId),cur);
                    sb.append(calPath(cur));
                    break;
                }
            }

            if(null!=cur.line2){
                queue.offer(cur.line2);
            }else{
                if(canAdd(userNode.parentId,cur)){
                    cur.line2 = new Node(userNode.id,parent(cur,userNode.parentId),cur);
                    sb.append(calPath(cur));
                    break;
                }
            }

            if(null!=cur.line3){
                queue.offer(cur.line3);
            }else{
                if(canAdd(userNode.parentId,cur)) {
                    cur.line3 = new Node(userNode.id, parent(cur, userNode.parentId), cur);
                    sb.append(calPath(cur));
                    break;
                }
            }
        }
        userNode.path = sb.toString();
    }
    //如果通过cur向上用fakeParent找不到parentId，说明二者无关系，不应该添加
    private boolean canAdd(Integer parentId, Node cur){
        Node node = cur;
        while(null!=node){
            if(node.id==parentId)
                return true;
            node = node.fakeParent;
        }
        return false;
    }

    private String calPath(Node node){
        String str = "";
        int i=0;
        while(null!=node){
            if(i==0){
                str = node.id+str;
            }else{
                str = node.id+ "," +str;
            }
            node = node.fakeParent;
            i++;
        }
        return str;
    }

    public Node buildTree(UserNode rootUserNode, List<UserNode> list) {
        Node root = new Node(rootUserNode.id);
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        int i = 0;
        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            for(int j=0;j<3;j++){
                if (i >= 0 && i < list.size()) {
                    UserNode userNode = list.get(i);
                    String path = userNode.path;
                    Integer parentId = userNode.parentId;
                    if (isEndEqualsId(path, cur.id)) {
                        Node line1 = new Node(userNode.id, parent(cur, parentId),cur);
                        queue.offer(line1);
                        if(j==0){
                            cur.line1 = line1;
                        }else if(j==1){
                            cur.line2 = line1;
                        }else{
                            cur.line3 = line1;
                        }
                        i++;
                    }
                }
            }

        }
        return this.root=root;
    }


    private Node parent(Node cur, Integer parentId) {
        if (parentId == cur.id)
            return cur;

        Node par = cur.fakeParent;
        while (null != par && par.id != parentId) {
            par = par.fakeParent;
        }
        return par;
    }

    private boolean isEndEqualsId(String path, Integer id) {
        int last = path.lastIndexOf(",") + 1;
        path = path.substring(last);
        if (path.equalsIgnoreCase("" + id))
            return true;

        return false;
    }
}
